//给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。 
//
// 测试用例的答案是一个 32-位 整数。 
//
// 子数组 是数组的连续子序列。 
//
// 
//
// 示例 1: 
//
// 
//输入: nums = [2,3,-2,4]
//输出: 6
//解释: 子数组 [2,3] 有最大乘积 6。
// 
//
// 示例 2: 
//
// 
//输入: nums = [-2,0,-1]
//输出: 0
//解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。 
//
// 
//
// 提示: 
//
// 
// 1 <= nums.length <= 2 * 10⁴ 
// -10 <= nums[i] <= 10 
// nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数 
// 
// Related Topics 数组 动态规划 👍 1714 👎 0

package leetcode.editor.cn;

class MaximumProductSubarray {
    public static void main(String[] args) {
        Solution solution = new MaximumProductSubarray().new Solution();
        solution.maxProduct(new int[]{-2, 0, -1, -1});
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
    /*public int maxProduct(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0] * nums[1], nums[1]);
        int max = dp[0];
        for (int i = 2; i < nums.length; i++) {
            if (nums[i] < 0) {
                dp[i] = Math.max()
            } else {
                dp[i] = Math.max(dp[i - 1] * nums[i], nums[i]);
                max = Math.max(max, dp[i]);
            }
        }

        return max;
    }*/

        /*public int maxProduct(int[] nums) {
            int[] maxDp = new int[nums.length];
            int[] minDp = new int[nums.length];
            maxDp[0] = nums[0];
            minDp[0] = nums[0];
            int max = nums[0];
            for (int i = 1; i < nums.length; i++) {
                maxDp[i] = Math.max(maxDp[i - 1] * nums[i], Math.max(nums[i], minDp[i - 1] * nums[i]));
                minDp[i] = Math.min(minDp[i - 1] * nums[i], Math.min(nums[i], maxDp[i - 1] * nums[i]));
                max = Math.max(max, maxDp[i]);
            }

            return max;
        } */

       /*public int maxProduct(int[] nums) {
            int[][] dp = new int[nums.length][2];
            dp[0][0] = nums[0];
            dp[0][1] = nums[0];
            int max = nums[0];
            for (int i = 1; i < nums.length; i++) {
                dp[i][0] = Math.max(dp[i - 1][0] * nums[i], Math.max(nums[i], dp[i - 1][1] * nums[i]));
                dp[i][1] = Math.min(dp[i - 1][1] * nums[i], Math.min(nums[i], dp[i - 1][0] * nums[i]));
                max = Math.max(max, dp[i][0]);
            }

            return max;
        }*/

        // 滚动数组优化
        public int maxProduct(int[] nums) {
            int minF = nums[0], maxF = nums[0], ans = nums[0];
            for (int i = 1; i < nums.length; i++) {
                // 需要记录，因为计算了maxF之后会覆盖上一次的，所以minF就不准确
                int mx = maxF, mn = minF;
                maxF = Math.max(mx * nums[i], Math.max(nums[i], mn * nums[i]));
                minF = Math.min(mn * nums[i], Math.min(nums[i], mx * nums[i]));
                ans = Math.max(ans, maxF);
            }
            return ans;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
